The present invention relates to a method and apparatus for detecting when a collision occurs between two or more binary data signal packets when they are received by a single binary data signal receiver.
Computers are widely used for computation, data processing, control and communication systems. Frequently, access to a computer is made by way of remote consoles or terminals each tying into the computer. The communications link between the terminals and the computer is advantageously established by using optical fibers because of their known properties of high signal speed, structural simplicity, low distortion, and isolation from interference.
Computer communications are characteristically in the form of short bursts of binary information. By taking advantage of the characteristics of computer communications, systems have been developed which allow many users to use a single computer at the same time and for different computers to communicate with one another over a single network.
Two switching techniques are generally used in computer communication systems to permit non-exclusive use of a computer. These switching techniques are known as the circuit switching technique and the packet switching technique. Data communications over the switched public telephone line are illustrative of the circuit switching technique, and the Ethernet system is typical of the packet switching technique.
The circuit switching technique establishes a connection between a computer and a terminal only when data is to be transmitted. However, because the time required to establish a connection may be very large compared to the actual time of a communication, especially in the case of a short communication, this technique is slow, inefficient and expensive.
In contrast, the packet switching technique maintains the communications connection at all times but uses it only to transmit data in the form of packets of binary information. Short communications are transmitted by a single packet while longer or bursty communications are transmitted by a series of packets. The packets are of a duration of about 60 microseconds, and if a communication cannot completely fit onto a single packet, more than one packet is transmitted separated by an interpacket gap of about 10 microseconds in duration. Data rates in the Ethernet system, for example, are 10 Megabits/second so that a single bit has a pulse width or duration of 100 nanoseconds and a packet contains about 6,000 bits.
The packet is typically divided into two primary sections, the header and the data, each of which has a different purpose. The header is the portion of the packet which is initially received and contains such information as the address to which the packet is to be sent, the address of the sender of the packet and other information that the particular system requires. Following the header is the data section in which the substance of the communication is contained either wholly for a short communication, or partially for a longer communication. The packet may include an additional section which follows the data section which contains information relating to error checks or to packet linking.
Because packets are transmitted from different transmitters at random time intervals, it is possible that packet collisions will occur because more than one packet is transmitted at the same time. When a collision of packets is detected, an instruction is sent to retransmit the original data so that another attempt may be made to receive the packet without a collision. If a collision of packets is not detected, the information transmitted is lost since the signal received is unintelligible as it is a sum of the overlapping packets.
Numerous techniques are known in the art for detecting a data collision. Ordinarily, these techniques are implemented at each terminal that is transmitting a data packet by examining the echoed back version of the transmitted signal. In U.S. Pat. No. 4,063,220, an exclusive OR gate at a signal transmitter compares the transmitted signal with the signal present on the communication cable, i.e. "echoed back", and aborts transmission when they are not the same. Another technique is to monitor the DC level of the signal received from the communication line and, if this level is higher than a specified threshold, assume there is a data collision.
Alternatively, as disclosed, for example, in U.S. Pat. No. 4,282,512, the receiver can look for data transitions that occur at timings different from those expected for the received data. U.S. Pat. No. 4,561,091 discloses a data communications receiver with a collision detection circuit for comparing a signal from a timing circuit with the received data signal and for producing a collision detection signal when the received data signal fails to change within the duration of the output signal from the timing circuit. The duration of the output signal from the timing circuit is equal to the longest data signal interval.
U.S. Pat. No. 4,560,984 discloses a method for detecting the collision of data packets in which a signal pulse, having an amplitude much larger than a data pulse, is substituted for the initial bit of the packet. The receiver tests for a pulse much larger than a data pulse. If two large signal pulses are received within a time period less than or equal to the sum of the duration of the packet and the time period between packets, a collision has occurred.
However, the above methods do not detect collisions for certain conditions. For example, the above methods do not detect the collision of two signals which arrive at the receiver at approximately the same time. In addition, the above methods do not always detect collisions that may arise involving an attenuated signal. In optical communication systems, it has been found that up to a 7 db loss (i.e. 80% decrease) of optical power may occur between the signal transmitted and the signal received. This loss of power may arise due to the length of transmission and the connectors or repeaters the signal passes through. In some cases of collision, the amplitude difference between the attenuated signal and the non-attenuated signal is so great that the attenuated signal has little effect on the non-attenuated signal and the collision is undetectable by current collision detection techniques.
U.S. application Ser. No. 157,545 filed Feb. 18, 1988 for METHOD AND APPARATUS FOR DETECTING THE COLLISION OF DATA PACKETS, addresses some of these problems and discloses a system in which the first twenty-four bits of the packet are modified to include collision detection data comprising an initial pulse having an amplitude sufficiently high to be detected even when attenuated and having a pulse width twice the normal data pulse width followed by a twenty bit code generated randomly at bit cell locations 5-24 in which ten pulses out of the twenty are at a high binary data signal level.
A collision is detected by determining if a large initial pulse has a pulse width larger than the generated pulse width, determining if a subsequent large pulse occurs within the remainder of the packet and by determining if more than ten pulses at bit cell locations 5-24 have a high binary data signal level.